package 动态规划.递归参数思考型;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/28 9:33
 */
public class lc1186删除子数组得到最大和 {

    /*
     一个思维性， 的转换性问题：

     - 给出一个 数组 nums[]
     那么 该数组 就 有一些 确定的元素,
     比如
     - 数组中的元素 和元素的 个数 是确定的!
     - 数组中的元素和是 确定的!

     - 这里的确定, 指的是, 你 进行排序或者其他的什么, 这种 ** 确定性 ** , 也不会发生变化!
     但是 **次序性** 就不一样了! 这个 会随着 排序的变化 , 发生变化!
     */





    /*
     那么,对于该题而言:
     A + B = sum
     sum 是固定的,
     A 和 B 会随着 所选元素的不同,而产生不同的结果!

     - 现在的问题:
     删除 A 让  B 最大

     - ① : 直接 求 B 最大
     - ② : 求 A 最小
     - 因为 A 是连续的 子数组,那么这题的方案已经出来了!

     */


    /*
     求 最小的 子数组的 和
     */
    public int solution(int nums[]){
        int sum = Arrays.stream(nums).sum();
        int min = 0 ,dp[] = new int[nums.length];
        dp[nums.length - 1] = nums[nums.length - 1];
        for(int i = nums.length - 2;i >= 0;i--){
            dp[i] = Math.min(dp[i - 1] + nums[i],nums[i]);
            min = Math.min(min,dp[i]);
        }

        return sum - min;
    }



    /*
     上面 的题意理解是错误的

     - 现在的 问题:
     选出一个子数组, 子数组不能为  空
     至少有 一个 元素

     - 删除 ,肯定选择一个负数给删掉, 这样的 话子数组的和会最大
     */
    public int maximumSum1(int[] arr) {
        int sum = Arrays.stream(arr).sum();
        if(sum < 0 && sum / arr.length == arr[0]){
            return arr[0];
        }

        // 这种简单的 依赖关系的, 可以使用滚动数组进行一个优化
        int ans = 0, min = 0, len = arr.length, dp[] = new int[len];
        dp[len - 1] = arr[len - 1];
        min = arr[len - 1];
        for(int i = len - 2; i>= 0;i--){
            dp[i] = Math.max(dp[i + 1] + arr[i], arr[i]);
            /*
            if(min < 0){
                ans = Math.max(ans,dp[i] - min);
            }
             */
            ans = Math.max(ans, min < 0 ? dp[i] - min : dp[i]);
            min = Math.min(min,arr[i]);
        }
        return ans;
    }

    /*
     Error
     */
    public int maximumSum(int[] arr) {
        int sum = Arrays.stream(arr).sum();
        if(sum < 0 && sum / arr.length == arr[0]){
            return arr[0];
        }

        // 这种简单的 依赖关系的, 可以使用滚动数组进行一个优化
        int ans = 0, min = 0, len = arr.length, dp[] = new int[len];
        dp[len - 1] = arr[len - 1];
        min = arr[len - 1];
        for(int i = len - 2; i>= 0;i--){
            if(dp[i + 1] + arr[i] < arr[i] ){
                dp[i] = arr[i];
                min = arr[i];
                ans = Math.max(ans,dp[i]);
            }
            else{
                dp[i] = dp[i + 1] + arr[i];
                min = Math.min(min, arr[i]);
                ans = Math.max(ans,min < 0 ? dp[i] - min : dp[i]);
            }
        }
        return ans;
    }




    /*
     卡在的点, 在那里呢?

       f(index, state): 表示 , 以 i 开头的所有子数组, 在 状态为 state的 时候 一个最大值
       state = 0 : 表示 不能删除, (其实 , 这种包括两种情况, 1. 以 i开头的子数组只有一个元素, 不能删除, 不能违反题意!  2. 只能删除 一次, 之前删除过的话, 之后就不能再删除了 )
       state = 1 : 表示必须要删除一个元素
     */
    public int function(int index,int state,int nums[],Integer dp[][]){
        if(index == nums.length - 1){
            return nums[index];
        }
        if(dp[index][state] != null){
            return dp[index][state];
        }
        // 开始根据 state 的值, 来进行一个抉择
        if(state == 0){
            return dp[index][state] = Math.max(function(index + 1,0,nums,dp) + nums[index],nums[index]);
        }
        // state  = 1
        // 此时 有两种 情况 1. 删除 index  2. 不删除 index , 删除 index 后面的
        return  dp[index][state] = Math.max(function(index + 1,0,nums,dp),function(index + 1,1,nums,dp) + nums[index]);

    }

    /*
     注意看递归函数, 参数 有两个变量, 这些老本行的东西, 不要忘记了!
     */
    public int solve(int nums[]){
        int ans = nums[0];
        Integer dp[][] = new Integer[nums.length][2];
        for(int i = 0;i < nums.length;i++){
//            ans = Math.max(ans, function(i,))
            ans = Math.max(ans,Math.max(function(i,0,nums,dp),function(i,1,nums,dp)));
        }
        return ans;
    }


}
